package j20251030;

public class Solution {
    boolean[][] col,row;
    boolean[][][] grid;
    public void solveSudoku(char[][] board) {
        col=new boolean[9][10];
        row=new boolean[9][10];
        grid=new boolean[3][3][10];
        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++){
                if(board[i][j]!='.'){
                    int num=board[i][j]-'0';
                    row[i][num]=col[j][num]=grid[i/3][j/3][num]=true;
                }
            }
        }
        dfs(board);
    }
    public boolean dfs(char[][] board){
        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++){
                if(board[i][j]=='.'){
                    //填数
                    for(int num=1;num<=9;num++){
                        if(!row[i][num]&&!col[j][num]&&!grid[i/3][j/3][num]){
                            board[i][j]=(char)(num+'0');
                            row[i][num]=col[j][num]=grid[i/3][j/3][num]=true;
                            if(dfs(board)==true) return true;
                            //恢复现场
                            board[i][j]='.';
                            row[i][num]=col[j][num]=grid[i/3][j/3][num]=false;
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
}
